<!DOCTYPE html>
<html>
<head>
<title>找出若干个数使其和最接近于M</title>
<meta http-equiv="Content-Type" content="text/html; charset=utf-8" />
<style type="text/css">
/* GitHub stylesheet for MarkdownPad (http://markdownpad.com) */
/* Author: Nicolas Hery - http://nicolashery.com */
/* Version: b13fe65ca28d2e568c6ed5d7f06581183df8f2ff */
/* Source: https://github.com/nicolahery/markdownpad-github */

/* RESET
=============================================================================*/

html, body, div, span, applet, object, iframe, h1, h2, h3, h4, h5, h6, p, blockquote, pre, a, abbr, acronym, address, big, cite, code, del, dfn, em, img, ins, kbd, q, s, samp, small, strike, strong, sub, sup, tt, var, b, u, i, center, dl, dt, dd, ol, ul, li, fieldset, form, label, legend, table, caption, tbody, tfoot, thead, tr, th, td, article, aside, canvas, details, embed, figure, figcaption, footer, header, hgroup, menu, nav, output, ruby, section, summary, time, mark, audio, video {
  margin: 0;
  padding: 0;
  border: 0;
}

/* BODY
=============================================================================*/

body {
  font-family: Helvetica, arial, freesans, clean, sans-serif;
  font-size: 14px;
  line-height: 1.6;
  color: #333;
  background-color: #fff;
  padding: 20px;
  max-width: 960px;
  margin: 0 auto;
}

body>*:first-child {
  margin-top: 0 !important;
}

body>*:last-child {
  margin-bottom: 0 !important;
}

/* BLOCKS
=============================================================================*/

p, blockquote, ul, ol, dl, table, pre {
  margin: 15px 0;
}

/* HEADERS
=============================================================================*/

h1, h2, h3, h4, h5, h6 {
  margin: 20px 0 10px;
  padding: 0;
  font-weight: bold;
  -webkit-font-smoothing: antialiased;
}

h1 tt, h1 code, h2 tt, h2 code, h3 tt, h3 code, h4 tt, h4 code, h5 tt, h5 code, h6 tt, h6 code {
  font-size: inherit;
}

h1 {
  font-size: 28px;
  color: #000;
}

h2 {
  font-size: 24px;
  border-bottom: 1px solid #ccc;
  color: #000;
}

h3 {
  font-size: 18px;
}

h4 {
  font-size: 16px;
}

h5 {
  font-size: 14px;
}

h6 {
  color: #777;
  font-size: 14px;
}

body>h2:first-child, body>h1:first-child, body>h1:first-child+h2, body>h3:first-child, body>h4:first-child, body>h5:first-child, body>h6:first-child {
  margin-top: 0;
  padding-top: 0;
}

a:first-child h1, a:first-child h2, a:first-child h3, a:first-child h4, a:first-child h5, a:first-child h6 {
  margin-top: 0;
  padding-top: 0;
}

h1+p, h2+p, h3+p, h4+p, h5+p, h6+p {
  margin-top: 10px;
}

/* LINKS
=============================================================================*/

a {
  color: #4183C4;
  text-decoration: none;
}

a:hover {
  text-decoration: underline;
}

/* LISTS
=============================================================================*/

ul, ol {
  padding-left: 30px;
}

ul li > :first-child, 
ol li > :first-child, 
ul li ul:first-of-type, 
ol li ol:first-of-type, 
ul li ol:first-of-type, 
ol li ul:first-of-type {
  margin-top: 0px;
}

ul ul, ul ol, ol ol, ol ul {
  margin-bottom: 0;
}

dl {
  padding: 0;
}

dl dt {
  font-size: 14px;
  font-weight: bold;
  font-style: italic;
  padding: 0;
  margin: 15px 0 5px;
}

dl dt:first-child {
  padding: 0;
}

dl dt>:first-child {
  margin-top: 0px;
}

dl dt>:last-child {
  margin-bottom: 0px;
}

dl dd {
  margin: 0 0 15px;
  padding: 0 15px;
}

dl dd>:first-child {
  margin-top: 0px;
}

dl dd>:last-child {
  margin-bottom: 0px;
}

/* CODE
=============================================================================*/

pre, code, tt {
  font-size: 12px;
  font-family: Consolas, "Liberation Mono", Courier, monospace;
}

code, tt {
  margin: 0 0px;
  padding: 0px 0px;
  white-space: nowrap;
  border: 1px solid #eaeaea;
  background-color: #f8f8f8;
  border-radius: 3px;
}

pre>code {
  margin: 0;
  padding: 0;
  white-space: pre;
  border: none;
  background: transparent;
}

pre {
  background-color: #f8f8f8;
  border: 1px solid #ccc;
  font-size: 13px;
  line-height: 19px;
  overflow: auto;
  padding: 6px 10px;
  border-radius: 3px;
}

pre code, pre tt {
  background-color: transparent;
  border: none;
}

kbd {
    -moz-border-bottom-colors: none;
    -moz-border-left-colors: none;
    -moz-border-right-colors: none;
    -moz-border-top-colors: none;
    background-color: #DDDDDD;
    background-image: linear-gradient(#F1F1F1, #DDDDDD);
    background-repeat: repeat-x;
    border-color: #DDDDDD #CCCCCC #CCCCCC #DDDDDD;
    border-image: none;
    border-radius: 2px 2px 2px 2px;
    border-style: solid;
    border-width: 1px;
    font-family: "Helvetica Neue",Helvetica,Arial,sans-serif;
    line-height: 10px;
    padding: 1px 4px;
}

/* QUOTES
=============================================================================*/

blockquote {
  border-left: 4px solid #DDD;
  padding: 0 15px;
  color: #777;
}

blockquote>:first-child {
  margin-top: 0px;
}

blockquote>:last-child {
  margin-bottom: 0px;
}

/* HORIZONTAL RULES
=============================================================================*/

hr {
  clear: both;
  margin: 15px 0;
  height: 0px;
  overflow: hidden;
  border: none;
  background: transparent;
  border-bottom: 4px solid #ddd;
  padding: 0;
}

/* TABLES
=============================================================================*/

table th {
  font-weight: bold;
}

table th, table td {
  border: 1px solid #ccc;
  padding: 6px 13px;
}

table tr {
  border-top: 1px solid #ccc;
  background-color: #fff;
}

table tr:nth-child(2n) {
  background-color: #f8f8f8;
}

/* IMAGES
=============================================================================*/

img {
  max-width: 100%
}
</style>
</head>
<body>
<h1>找出若干个数使其和最接近于M</h1>
<hr />
<h2>1. 题目</h2>
<pre><code>给定一个由正数组成的列表alts，一个目标数M
需要从alts中选取若干个备选数，使其和为M
若找不到和刚好与M相等的备选数列表，则返回和与M最接近的备选数列表
若有多个结果，返回一个即可
eg1.
    输入: 
        alts = [10, 9, 8, 7, 6, 5]
        M = 22
    输出: [10, 7, 5] 或 [9, 8, 5]

eg2.
    输入: 
        alts = [10, 7, 6, 3]
        M = 18
    输出: [10, 7]

拓展:
    若alts中同时有正数和负数呢
</code></pre>

<h2>2. 思路：</h2>
<pre><code>先考虑alts中只有正数的情况

由于只需要返回一个可行结果或最优结果，那么可以从大到小在alts中搜索备选数，
当备选数之和等于M时结束搜索，否则新加入或修改已经加入的备选数

假设已经有备选数列表A，其和为N，与M之差为d=M-N，
则选择下一个备选数时应选择小于等于d且与d最接近的数

若新加入一个数之后，发现从剩下的数中肯定找不到可行解了，则说明前面加入的那个数时错误的，应换掉

例如eg1.的搜索过程
    step1: A = [10], N = 10, d = 12 (22-10), 剩下的数中9与12最接近，下一步加入9
    setp2: A = [10, 9], N = 19, d = 3, 剩下的数中没有小于等于3的，说明9的加入是错误的，
           应换一个比9小的，最接近的是8，换8
    step3: A = [10, 8], N = 18, d = 4, 剩下的数中没有小于等于4的，说明8的加入是错误的，
           应换一个比8小的，最接近的是7，换7
    step4: A = [10, 7], N = 17, d = 4, 剩下的数中与5最接近的是5，加入
    step5: A = [10, 7, 5], N = 22, d = 0, 结束


当alts中有负数时，不能根据差d选最接近的下一个备选数，
因为中间可能有值满足可行解但是被跳过了，
解决办法是不用d选择下一个备选数，直接选跟上小于等于上一个备选数且与之最接近的数即可
</code></pre>

<h2>3. Python代码：</h2>
<pre><code># -*- coding: utf-8 -*-


def FindAddends_BigFirst(M, alts, tol=0.0, max_loop=1000000): 
    '''
    从给定的列表alts（可以有负数）中选取若干个数，使其和最接近M

    思路: 大的备选数优先，从大到小依次加入备选数
         若加入新值之后找不到理想解，则删除最后加入的值，继续添加下一个更小的备选数
         下一个备选数确定方式：
             当alts中只有正数时，剩下的数中与剩余和（目标和减去当前和）最接近的数
             当alts中有负数时，直接取比最后加进去的数更小的数（搜索速度会变慢很多）

    Args:
        M: 目标和
        alts: list，备选数列表
        max_loop: 搜索次数限制

    Returns:
        choseds_best: list，最优备选数列表
    '''

    alts.sort() # 升序（大的数优先进入）
    all_postive = all([x &gt;= 0 for x in alts])

    # 初始化
    # idx_last记录最新进入的数的索引号
    # chosed_idxs记录备选中的数的索引号
    # chosed_addends保存被选中的数
    # choseds_best保存最优结果
    # now_sum为chosed_addends求和
    idx_last = len(alts) - 1
    chosed_idxs = [idx_last]
    chosed_addends = [alts[idx_last]]
    choseds_best = []
    now_sum = alts[idx_last]

    # 搜索过程
    loop_count = 0
    while loop_count &lt; max_loop:
        loop_count += 1

        # 更新最优解
        if abs(M - now_sum) &lt; abs(M - sum(choseds_best)):
            choseds_best = chosed_addends.copy()

        # 结束条件
        if M == now_sum:
            print('找到最优解，结束搜索。')
            break

        # 无最优解（搜索到最小值且只剩它一个备选数），结束搜索
        if idx_last == 0 and len(chosed_idxs) == 1:
            print('无最优解，结束搜索。')
            break

        # 刚好搜索到最小值且不是最优解，此时去掉最小值并更改最小值前面一个进去的值
        if idx_last == 0:
            idx_last = chosed_idxs[-2] - 1
            del chosed_idxs[-2:]
            chosed_idxs.append(idx_last)
            del chosed_addends[-2:]
            chosed_addends.append(alts[idx_last])
            now_sum = sum(chosed_addends)
            continue

        # 下一个备选数
        if not all_postive:
            idx_last -= 1
        else:
            idx_last = backfind_sml1st_idx(M-now_sum, alts[0:idx_last])

        # 保留最后一个加进去的数情况下找不到最优解，更改最后进去的那个数
        if idx_last &lt; 0:
            idx_last = chosed_idxs[-1] - 1
            chosed_idxs[-1] = idx_last
            chosed_addends[-1] = alts[idx_last]
            now_sum = sum(chosed_addends)
            continue

        chosed_idxs.append(idx_last)
        chosed_addends.append(alts[idx_last])
        now_sum += alts[idx_last]

    return choseds_best


def backfind_sml1st_idx(M, alts):
    '''
    alts（已升序排列）从后往前搜索，返回第一个小于等于M的数的索引
    '''
    if len(alts) == 0:
        return -1    
    idx = len(alts) - 1
    while idx &gt;= 1 and alts[idx] &gt; M:
        idx -= 1
    return idx


if __name__ == '__main__':    
    alts = [22, 15, 14, 13, 7, 6.1, 5, 21.5, 100]
    M = 22 + 21 + 4.1
    print(FindAddends_BigFirst(M, alts, max_loop=10000000))

    alts = [200, 107, 100, 99, 98, 6, 5, 3, -1, -20, -25]
    M = 100 + 6 - 25
    print(FindAddends_BigFirst(M, alts, max_loop=10000000))

    alts = [100, -100, -105, -102, -25, -30, -1]
    M = -26
    print(FindAddends_BigFirst(M, alts, max_loop=10000000))

    alts = [10, 9, 8, 7, 6, 5]
    M = 17
    print(FindAddends_BigFirst(M, alts, max_loop=10000000))

    alts = [10, 9, 8, -7, -6, -5]
    M = 3
    print(FindAddends_BigFirst(M, alts, max_loop=10000000))

    alts = [10, 7, 6, 3]
    M = 18
    print(FindAddends_BigFirst(M, alts, max_loop=10000000))

    alts = [10, 7, 6, 3]
    M = 12
    print(FindAddends_BigFirst(M, alts, max_loop=10000000))

    alts = [10, 9, 8, 7, 6, 5, 3]
    M = 14
    print(FindAddends_BigFirst(M, alts, max_loop=10000000))

    alts = [10, 9, 8, 7, 6, 5]
    M = 22
    print(FindAddends_BigFirst(M, alts, max_loop=10000000))
</code></pre>


</body>
</html>
<!-- This document was created with MarkdownPad, the Markdown editor for Windows (http://markdownpad.com) -->
